#include "staticsearch.h"
#include <stdlib.h>
#include <stddef.h>

StaticSearch::StaticSearch()
{

}

int sequential_Search(int *array, int length, int key)
{
    if(array==NULL || length<2)
        return -1;
    for(int i=0;i<length;++i){
        if(array[i]==key)
            return i;
    }
    return -1;
}
//有哨兵的顺序查找，当数组的第一个元素为空的时候可以使用
int sequential_Search2(int *array, int length, int key)
{
    if(array==NULL || length<2)
        return -1;

    array[0]=key;
    int index=length;
    while(array[index] != key)
        --index;
    return index;
}
//折半查找
int Binary_Search(int *array, int length, int key)
{
    if(array==NULL || length<2)
        return -1;

    int low,mid,high;
    low=0;
    high=length-1;
    while(low<=high){       //需要考虑相等的情况
        mid=(low+high)/2;
        if(array[mid]>key)
            high=mid-1;
        else if(array[mid] < key)
            low=mid+1;
        else                //找到相等的情况
            return mid;
    }
    return -1;
}

int Interpolation_Search(int *array, int length, int key)
{
    if(array==NULL || length<2)
        return -1;

    int low=0;
    int high=length-1;
    int mid;
    while(low<=high){
        mid=low+(high-low)*(key-array[low])/(array[high]-array[low]);
        if(key>array[mid])
            low=mid+1;
        else if(key<array[mid])
            high=mid-1;
        else
            return mid;
    }
    return -1;
}

int Fabonacci_Search(int *array, int length, int key)
{
    if(array==NULL || length<2)
        return -1;

    int low=0;
    int high=length-1;
    int mid=0;

    int FIndex=0;
    int *FArray=FibonacciCreate(length);
    //确定斐波那契数组下标
    while(length > FArray[FIndex]-1)
        ++FIndex;

    //建立临时数组
    int *tmpArray=(int*)malloc(sizeof(FArray[FIndex]-1));
    //将要查找的数据放到临时数组中
    for(int i=0;i<length;++i)
        tmpArray[i]=array[i];
    //因为确定的斐波那契数大于length，所以数组最后补充数据array[high]
    for(int i=high;i<FArray[FIndex]-1;++i)
        tmpArray[i]=array[high];

    //开始循环查找
    while(low<=high){
        //前半部分有FArray[FIndex-1]个元素，由于下表从0开始所以需要-1
        mid=low+FArray[FIndex-1]-1;
        if(key > tmpArray[mid]){
            high=mid-1;
            // （全部元素） = （前半部分）+（后半部分）
            // f[k] = f[k-1] + f[k-2]
            // 因为前半部分有f[k-1]个元素，所以 k = k-1
            FIndex=FIndex-1;
        }
        else if(key < tmpArray[mid]){
            low=mid+1;
            // （全部元素） = （前半部分）+（后半部分）
            // f[k] = f[k-1] + f[k-2]
            // 因为后半部分有f[k-2]个元素，所以 k = k-2
            FIndex=FIndex-2;
        }
        else{
            // 如果为真则找到相应的位置
            if(mid<=high)
                return mid;
            else
                // 出现这种情况是查找到补充的元素
                // 而补充的元素与high位置的元素一样
                return high;
        }
    }
    return -1;
}

int *FibonacciCreate(int length)
{
    int *array=(int*)malloc(sizeof(int));
    array[0]=1;
    array[1]=1;
    for(int i=2;i<length;++i){
        array[i]=array[i-1]+array[i-2];
    }
    return array;
}
